package leetcode_141_160;

import utils.ListNode;

import java.util.HashSet;

public class detectCycle_142 {
    /**
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     */
    public ListNode detectCycle(ListNode head) {
        /**
         * 依然最简单的思路，建立hash表遍历所有元素
         * 3ms
         */
        HashSet<ListNode> set=new HashSet<>();
        while(head!=null){
            if(!set.add(head))
                return head;
            head=head.next;
        }
        return null;
    }

    public ListNode detectCycle2(ListNode head) {
        /**
         * 高解思路
         * 分析此时 fast 与 slow 走过的步数关系
         * 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点
         * 设两指针分别走了 f，s 步相遇，则有：
         * fast 走的步数是 slow 步数的 2 倍，即 f=2s；（解析： fast 每轮走 2 步）
         * fast 比 slow 多走了 n 个环的长度，即 f=s+nb；
         * （解析： 双指针都走过 a 步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走 环的长度整数倍 ）。
         * 得s=nb
         * 走到链表入口节点时的步数 是：k=a+nb
         * 只要想办法让 slow 再走 a 步停下来，就可以到环的入口
         *
         * 如何判断是否走到了入口节点？
         * 只需要再设置一个root节点从头开始一步一步走
         * 此时slow和root均走a步即可到达入口
         * slow和root为同一节点时，即为入口节点
         * 0ms
         */
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        //这里先执行一次，避免直接跳出循环
        do {     //快慢指针相遇说明有环
            if (fast == null || fast.next == null) {  //链路有终点无环
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }while (slow != fast);

        while (slow != head) {     //指针相遇说明为入口节点
            slow = slow.next;
            head = head.next;
        }
        return slow;
    }
}
